#include <limits.h>

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct TreeNode
{
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution
{
 public:
  // 112.路径总和
  bool hasPathSum(TreeNode* root, int sum)
  {
    if (root == NULL)
    {
      if (sum == 0)
      {
        return true;
      }
      return false;
    }

    return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    // sum没有回溯，但是在调试的过程中，系统栈自动给sum回溯了，因为sum是临时遍历，每进入一个递归重新生成一个sum
    // 当递归返回的时候，上一层的递归中的临时sum还保留着
  }

  // 113.路径总和2：这个要回溯答案了
  vector<vector<int>> pathSum(TreeNode* root, int sum)
  {
    vector<int> track;
    vector<vector<int>> res;
    dfs1(root, sum, track, res);

    return res;
  }

  void dfs1(TreeNode* root, int sum, vector<int>& track, vector<vector<int>>& res)
  {
    if (root == NULL)
    {
      return;
    }
    if (sum == root->val && root->left == NULL && root->right == NULL)
    {
      track.push_back(root->val);
      res.push_back(track);
      track.pop_back();
      return;
    }

    // 这种return会有问题，如果没有满足条件的情况，整个岂不是没有return了
    // if (sum == root->val)
    // {
    //   res.push_back(track);
    //   return;
    // }

    track.push_back(root->val);
    // if (root->left)
    dfs1(root->left, sum - root->val, track, res);
    // if (root->right)
    dfs1(root->right, sum - root->val, track, res);
    track.pop_back();
  }

  // 124.二叉树中的最大路径和
  int maxPathSum(TreeNode* root)
  {
    dfs2(root);
    return res_124;
  }

  int dfs2(TreeNode* root)
  {
    if (root == NULL) return 0;
    // 递归计算左右子节点的最大贡献值
    // 只有在最大贡献值大于 0 时，才会选取对应子节点
    // 即走不走b->d 或 b->e
    int left = max(dfs2(root->left), 0);  // 此时root->left作为一个子节点往下递归
    int right = max(dfs2(root->right), 0);

    // 节点b的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
    int priceNewpath = root->val + left + right;

    // 更新答案
    res_124 = max(res_124, priceNewpath);

    // 返回节点的最大贡献值
    // 当前节点为n,对于当前节点来说，最大值可以为n+left,n+right,n,n+left+right
    // 上面四项中的一个，但是返回是不能返回第四个的，那种路径是不成立的
    // 因为你要往下递归，所以不能返回不成立的路径
    return root->val + max(left, right);
  }

  // 437. 路径总和 III
  int pathSum2(TreeNode* root, int sum)
  {
    if (NULL == root)
    {
      return 0;
    }

    dfs3(root, sum);

    // 也可能不从root发起dfs，从这棵数的任何节点发起DFS都是可以的
    pathSum(root->left, sum);
    pathSum(root->left, sum);
    return res_437;
  }

  void dfs3(TreeNode* root, int sum)
  {
    if (root == NULL)
    {
      return;
    }

    if (root->val == sum)
    {
      res_437++;
      return;
    }

    dfs3(root->left, sum - root->val);

    dfs3(root->right, sum - root->val);

    return;
  }

  // 46. 全排列
  vector<vector<int>> permute(vector<int>& nums)
  {
    vector<int> track;
    vector<vector<int>> res;
    int n = nums.size();
    if (0 == n)
    {
      return res;
    }
    vector<bool> used(n, false);
    dfs4(nums, res, track, used, 0);
    return res;
  }

  void dfs4(vector<int>& nums, vector<vector<int>>& res, vector<int>& track, vector<bool>& used,
            int depth)
  {
    if (depth == nums.size())
    {
      res.push_back(track);
      return;
    }

    for (int i = 0; i < nums.size(); i++)
    {
      if (used[i] == true)
      {
        continue;
      }
      track.push_back(nums[i]);
      used[i] = true;
      // depth自动回溯到上一次调用的栈
      dfs4(nums, res, track, used, depth + 1);
      used[i] = false;
      track.pop_back();
    }
  }

  // 47.全排列2，加剪枝
  // if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false)
  // {
  //   continue;
  // }

  // 39.组合总和
  vector<vector<int>> combinationSum(vector<int> candidates, int target)
  {
    vector<int> track;
    vector<vector<int>> res;
    sort(candidates.begin(), candidates.end());
    dfs5(res, track, candidates, target, 0);

    return res;
  }

  void dfs5(vector<vector<int>>& res, vector<int>& track, const vector<int>& candidates, int target,
            int start)
  {
    int n = candidates.size();

    if (target == 0)
    {
      res.push_back(track);
      return;
    }
    for (int i = start; i < n; i++)
    {
      if (target - candidates[i] < 0)
      {
        break;
      }
      track.push_back(candidates[i]);
      dfs5(res, track, candidates, target - candidates[i], i);

      track.pop_back();
    }
  }

  // 40. 组合总和 II
  vector<vector<int>> combinationSum2(vector<int>& candidates, int target)
  {
    vector<int> track;
    vector<vector<int>> res;
    vector<bool> used(candidates.size(), false);
    sort(candidates.begin(), candidates.end());
    dfs6(res, track, candidates, target, used, 0);

    return res;
  }

  void dfs6(vector<vector<int>>& res, vector<int>& track, const vector<int>& candidates, int target,
            vector<bool>& used, int start)
  {
    int n = candidates.size();
    if (target == 0)
    {
      res.push_back(track);
      return;
    }

    for (int i = start; i < n; i++)
    {
      if (used[i] == true)
      {
        continue;
      }
      if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false)
      {
        continue;
      }

      if (target - candidates[i] < 0)
      {
        break;
      }
      used[i] = true;
      track.push_back(candidates[i]);
      dfs6(res, track, candidates, target - candidates[i], used, i);
      used[i] = false;
      track.pop_back();
    }
  }

  // 77.组合
  vector<vector<int>> combine(int n, int k)
  {
    vector<int> track;
    vector<vector<int>> res;
    dfs7(res, track, n, k, 1);
    return res;
  }

  void dfs7(vector<vector<int>>& res, vector<int>& track, int n, int k, int start)
  {
    if (track.size() == k)
    {
      res.push_back(track);
      return;
    }

    for (int i = start; i <= n; i++)
    {
      track.push_back(i);
      dfs7(res, track, n, k, i + 1);
      track.pop_back();
    }
  }

  // 78.子集
  vector<vector<int>> subsets(vector<int>& nums)
  {
    vector<int> track;
    vector<vector<int>> res;
    dfs8(nums, res, track, 0);
    return res;
  }

  void dfs8(vector<int>& nums, vector<vector<int>>& res, vector<int>& track, int start)
  {
    res.push_back(track);

    for (int i = start; i < nums.size(); i++)
    {
      track.push_back(nums[i]);
      dfs8(nums, res, track, i + 1);
      track.pop_back();
    }

    return;
  }

  // 90.求子集2
  vector<vector<int>> subsetsWithDup(vector<int>& nums)
  {
    sort(nums.begin(), nums.end());
    vector<int> track;
    vector<vector<int>> res;
    vector<bool> used(nums.size(), false);
    dfs9(nums, res, track, 0, used);
    return res;
  }

  void dfs9(vector<int>& nums, vector<vector<int>>& res, vector<int>& track, int start,
            vector<bool>& used)
  {
    res.push_back(track);

    for (int i = start; i < nums.size(); i++)
    {
      if (used[i] == true)
      {
        continue;
      }
      if (i > 0 && nums[i - 1] == nums[i] && used[i - 1] == false)
      {
        continue;
      }
      track.push_back(nums[i]);
      used[i] = true;
      dfs9(nums, res, track, i + 1, used);
      track.pop_back();
      used[i] = false;
    }
  }

  // 60.第k個排列
  string getPermutation(int n, int k)
  {
    vector<bool> isUsed(n + 1, false);  // 用于标记每个数是否用过，为了从1~n,所以容量是n+1
    string res = "";                    // 用于返回的结果排列序列

    dfs10(isUsed, res, n, k);
    return res;
  }

  void dfs10(vector<bool>& isUsed, string& res, int n, int k)
  {
    int res_len = res.size();
    if (res_len == n)
    {
      return;  // 结束条件，当前排列已经结束
    }

    // 换一种说法是，比如以1开头的全排列有(n-1)!,刚开始res_len==0
    int remain_fac = factorial(n - res_len - 1);

    for (int i = 1; i <= n; i++)  // 遍历[1,n]
    {
      if (isUsed[i]) continue;

      if (remain_fac < k)
      {
        k -= remain_fac;
        continue;
      }
      // 此时remain_fac>k
      res = res + static_cast<char>('0' + i);
      isUsed[i] = true;
      dfs10(isUsed, res, n, k);
    }
  }

  int factorial(int n)
  {
    int res = 1;
    while (n > 0)
    {
      res *= n;
      n--;
    }
    return res;
  }

  // 93.复原IP地址
  vector<string> restoreIpAddresses(string s)
  {
    string track = "";
    vector<string> res;
    // 如果长度不够，不搜索
    if (s.length() < 4 || s.length() > 12)
    {
      return res;
    }
    int pointNum = 0;
    dfs11(track, res, s, 0, pointNum);
    return res;
  }

  void dfs11(string& track, vector<string>& res, string s, int start, int pointNum)
  {
    if (pointNum == 3)
    {
      // 逗点数量为3时，分隔结束
      // 判断第四段子字符串是否合法(最后一段)，如果合法就放进result中

      if (isValid2(s.substr(start, s.size() - start)))
      {
        string t = track + s.substr(start, s.size() - start);
        res.push_back(t);
      }
      return;
    }

    // 从起始位置开始构造字段字符串串
    // start:[0,size() ) 起点
    // 截取终点 end: [1, size()]
    for (int end = start + 1; end <= s.length(); end++)
    {
      string tmp = s.substr(start, end - start);
      // 判断 [startIndex,i] 这个区间的子串是否合法
      if (!isValid2(tmp))
      {
        return;
      }
      // 合法，在i的后面插入一个逗点
      tmp += ".";
      int length = track.size();
      track += tmp;
      dfs11(track, res, s, end, pointNum + 1);
      // 回溯时删除
      track = track.substr(0, length);  // 把tmp与.删除
    }
  }

  bool isValid2(string tmp)
  {
    int sum = 0;
    for (int i = 0; i < tmp.length(); i++)
    {
      if ('0' <= tmp[i] && tmp[i] <= '9')
      {
        sum = (tmp[i] - '0') + sum * 10;
      }
      else
      {
        return false;
      }
    }
    if (sum == 0 && tmp.size() != 1)
    {
      return false;
    }
    if (sum != 0 && tmp[0] == '0')
    {
      return false;
    }
    if (sum > 255 || sum < 0)
    {
      return false;
    }

    return true;
  }

  // 131.分割回文串
  vector<vector<string>> partition(string s)
  {
    // 用DFS, 回溯需要用在track，因为track是全局变量，每一个递归子树产生的结果在track
    // push进res后，需要撤销选择
    vector<vector<string>> res;
    vector<string> track;
    if (0 == s.length()) return res;
    backtrack(res, track, s, 0);
    return res;
  }

  void backtrack(vector<vector<string>>& res, vector<string>& track, string s, int start)
  {
    if (start == s.length())
    {
      res.push_back(track);
      return;
    }
    // 从起始位置开始构造字段字符串串
    // start:[0,size() ) 起点
    // 截取终点 end: [1, size()]
    for (int end = start + 1; end <= s.length(); end++)
    {
      if (isPalind(s.substr(start, end - start)))
      {
        track.push_back(s.substr(start, end - start));  // 递归树第一层for循环 取 a ab aab
        backtrack(res, track, s, end);  // 进入第一层for循环a的递归子树：a->ab
        track.pop_back();  // 针对第一层for循环a pop掉 准备进入第一层for循环 ab的递归子树
      }
    }
  }

  bool isPalind(string s)
  {
    int left = 0;
    int right = s.length() - 1;
    while (left < right)
    {
      if (s[left] != s[right])
      {
        return false;
      }
      left++;
      right--;
    }
    return true;
  }

  // 132.分割回文串2
  int minCut(string s)
  {
    vector<vector<string>> res;
    vector<string> track;
    if (0 == s.length()) return 0;
    dfs12(res, track, s, 0, 0);
    return min_num_132;
  }

  void dfs12(vector<vector<string>>& res, vector<string>& track, string s, int start, int depth)
  {
    // base case
    if (start == s.length())
    {
      if (depth - 1 < min_num_132)
      {
        min_num_132 = depth - 1;
      }
      res.push_back(track);
      return;
    }
    for (int end = start + 1; end <= s.length(); end++)
    {
      if (isPalind(s.substr(start, end - start)))
      {
        track.push_back(s.substr(start, end - start));  // 递归树第一层for循环 取 a ab aab
        dfs12(res, track, s, end, depth + 1);  // 进入第一层for循环a的递归子树：a->ab
        track.pop_back();  // 针对第一层for循环a pop掉 准备进入第一层for循环 ab的递归子树
      }
    }
  }

 private:
  int res_124 = INT_MIN;
  int res_437 = 0;
  int min_num_132 = INT_MAX;
};

int main()
{
  // TreeNode *a1 = new TreeNode(5);
  // TreeNode *a2 = new TreeNode(4);
  // TreeNode *a3 = new TreeNode(8);
  // a1->left = a2;
  // a1->right = a3;

  // TreeNode *a4 = new TreeNode(11);
  // TreeNode *a5 = new TreeNode(13);
  // TreeNode *a6 = new TreeNode(4);
  // a2->left = a4;
  // a2->right = NULL;
  // a3->left = a5;
  // a3->right = a6;
  // TreeNode *a7 = new TreeNode(7);
  // TreeNode *a8 = new TreeNode(2);
  // TreeNode *a9 = new TreeNode(5);
  // a4->left = a7;
  // a4->right = a8;
  // a5->left = NULL;
  // a5->right = NULL;
  // a6->left = NULL;
  // a6->right = a9;

  // a7->left = NULL;
  // a7->right = NULL;
  // a8->left = NULL;
  // a8->right = NULL;
  // a9->left = NULL;
  // a9->right = NULL;

  Solution solute;
  vector<int> nums = {1, 2, 3, 4};
  // int target = 8;
  string s = "aab";
  int res = solute.minCut(s);

  return 0;
}